#include<iostream>
#include<vector>
using namespace std;

//记忆主搜索01：菲波那切数列
// class Solution1 {
// public:
//     //vector<int> memo=vector<int>{32,-1};
//     int memo[32];
//     int fib(int n) 
//     {
//         for(int i=0;i<32;i++)
//         {
//             memo[i]=-1;
//         }
//         return dfs(n);        
//     }

//     int dfs(int n)
//     {
//         if(memo[n]!=-1) return memo[n];
//         if(n==1||n==0)  return n;
//         memo[n]=dfs(n-1)+dfs(n-2);
//         return memo[n];
//     }
// };

//动态规划
class Solution1 {
public:
    int dp[32];
    int fib(int n) 
    {
        dp[0]=0;
        dp[1]=1;
        for(int i=0;i<=n;i++)
        {
            if(i>1)
                dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];       
    }
};


//记忆化搜索02、；不同路劲
// //记忆化搜索方法
// class Solution2 {
// public:
//     //int ret=0;
//     //int dx[2]={-1,0};
//     //int dy[2]={0,-1};
//     //map<vector<int>,int> memo;
//     vector<vector<int>> memo;
//     int uniquePaths(int m, int n) 
//     {
//         memo=vector<vector<int>>(m+1,vector<int>(n+1,-1));
//         return dfs(m,n);
//     }

//     int dfs(int m,int n)
//     {
//         if(memo[m][n]!=-1)   return memo[m][n];
//         if(m>=2&&n>=2)
//             memo[m][n]=dfs(m-1,n)+dfs(m,n-1);
//         else
//             memo[m][n]=1;
//         return memo[m][n];
//     }
// };

//动态规划方法
class Solution2 {
public:

    int uniquePaths(int m, int n) 
    {
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        dp[1][1]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i!=1||j!=1)
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }        
        return dp[m][n];
    }
};


//记忆化搜索03：最长递增子序列
//记忆化搜索
// class Solution3 {
// public:
//     int m=0;
//     //map<int,int> memo;
//     vector<int> memo;
//     int lengthOfLIS(vector<int>& nums) 
//     {        
//         int ret=0;
//         m=nums.size();
//         memo.resize(m);
//         for(int i=0;i<m;i++)
//         {
//             ret=max(ret,dfs(nums,i));
//         }
//         return ret;
//     }
//     int dfs(vector<int>& nums,int pos)
//     {
//         if(memo[pos]!=0) return memo[pos];
//         //if(memo.count(pos)) return memo[pos];
//         int ret=1;
//         for(int i=pos+1;i<m;i++)
//         {
//             if(nums[i]>nums[pos])
//             {
//                 //ret = dfs(nums,i)+1;
//                 ret = max(ret,dfs(nums,i)+1);
//             }
//         }
//         memo[pos]=ret;
//         return ret;
//     }
// };
 
// 动态规划方法
class Solution3 {
public:
    int m=0;
    int ret=0;
    vector<int> dp;
    int lengthOfLIS(vector<int>& nums) 
    {        
        m=nums.size();
        dp.resize(m);
        for(int i=0;i<m;i++)
            dp[i]=1;
        for(int i=m-1;i>=0;i--)
        {
            for(int j=i+1;j<m;j++)
            {
                if(nums[j]>nums[i])
                    dp[i]=max(dp[i],dp[j]+1);
            }
            ret=max(ret,dp[i]);
        }
        return ret;
    }
};







int main()
{
    return 0;

}

